Wireless networks have become increasingly important and popular because mobility is supported along with many of the sophisticated applications offered by fixed wired networks. Wireless networks include traditional cellular networks with radio base stations coupled to a radio network infrastructure. A mobile terminal communicates with one or more base stations within range, and as the mobile moves out of range, a handover procedure to another base station may be performed to maintain continuous communication. Another type of wireless network is a mesh network. A mesh network handles many-to-many connections and is capable of dynamically optimizing these connections.
Wireless mesh networks are commonly known as wireless “ad hoc” networks that usually consist of mobile, battery-operated computing devices that communicate over a wireless medium. The network does not rely on fixed routers, and all of the nodes are capable of movement and can be connected dynamically in an arbitrary manner. Each node functions as a router that discovers and maintains routes to other nodes in the ad hoc network. A route is the path used to deliver one or more packets between a source node and a destination node. The route may contain one or more “hops.” A hop corresponds to a direct transmission from one node to another node without any intervening nodes. Examples of wireless technologies with ad hoc capability include IEEE 802.11 wireless local area networks (WLANs) and Bluetooth personal area networks (PANs).
Two types of routing protocols are generally employed in wireless mesh networks: table-driven routing protocols and source-initiated, on-demand routing protocols. Table-driven routing protocols attempt to maintain consistent, up-to-date routing information from each node to every other node in the network via periodic updates from all the other nodes in the network, irrespective of the fact that the network may not be active in terms of data traffic. For the on-demand approach, a request for routes to a destination is sent only if the source node has data packets to be sent to that destination node. Example table-driven ad hoc routing protocols include open shortest path first (OSPF) routing, destination-sequenced distance-vector routing, clusterhead gateway switch routing, and wireless routing protocol. Examples of source-initiated, on-demand routing include ad hoc on-demand distance vector routing or dynamic source routing, temporary order routing, associativity-based routing, and signal stability routing.
In open shortest path first (OSPF) routing, each wireless node maintains an identical database describing the network topology. From this database, a routing table is calculated by constructing a shortest path tree. The shortest path is that with the lowest cumulative “cost.” For a radio link or hop, the “cost” may be measured as the inverse of the expected data rate over that radio hop. As a result, low data rates are high cost because they result in longer times to transmit packets. OSPF was initially designed for fixed networks, but wireless routing protocol (WRP) and dynamic source routing (DSR) are similar in their route selection approach for wireless networks.
Wireless ad hoc networks must deal with certain limitations associated with the wireless communications medium including power/interference limitations, low bandwidth, and high error rates. Because wireless network nodes are typically battery-operated and because the capacity of a radio communications network is limited by the shared spectrum, routing protocols that attempt to find minimum energy routing path are of particular interest. Energy efficient routing schemes can greatly reduce energy consumption at the nodes, leading to longer battery life, as well as improve the network capacity by reducing the interference in the network. Table-driven routing schemes are generally more expensive in terms of energy consumption as compared to on-demand schemes because of the large overhead required to maintain the various tables. But minimum energy routing techniques should not only be focused on battery saving of the mobile nodes. Such routing algorithms should also try to improve network capacity.
Most wireless ad-hoc networks, and particular those that employ IEEE 801.11, share a radio frequency in time, and the same frequency is used both to transmit and receive. To coordinate using the shared frequency medium, some sort of protocol is employed. For example, carrier sense multiple access with collision avoidance (CSMA/CA) requires that a node wanting to transmit a packet must “listen” to ensure that no other node is transmitting. If the channel is clear for a certain time period, the node can transmit the packet directly; otherwise, the node sets a random “back off” timer. When the timer expires, the node transmits. A clear channel assessment (CCA) function may be employed to determine whether the common frequency is available. A CCA function usually includes both carrier sensing and energy detection. If either is triggered, the common frequency is considered busy. Carrier sensing is triggered when a receiver is able to detect another node's transmitted signal. The energy detection mechanism is triggered when the total received energy (regardless of the source) is above a threshold.
The inventors recognized that there are several factors that must be considered to obtain an optimal energy routing scheme. First, it is important to reduce the number of nodes refraining from transmitting over the common frequency due to a busy indication, e.g., a clear channel assessment (CCA) busy indication. Second, it is also important to reduce the length of time that each node must wait before it can transmit over the common channel. Although selecting the shortest length path as the shortest time delay path may improve battery saving, it may not optimize the network capacity. Wireless networks are interference limited. Transmission power is in most scenarios not equal to the interference caused by a particular transmission at a particular power. Indeed, nodes may be affected by transmission-based interference even if they are not within range/communication distance of the transmitting node, i.e., the nodes are still within interference distance.
A third consideration is the specific transmission conditions for the next hop transmission. For example, based on current radio conditions, the node will select a particular modulation and coding scheme for the transmission that adapts to those current conditions. That modulation and coding scheme establish the data transmission rate which should preferably be accounted for to estimate the node's transmission time and transmission energy over the next hop.
Another important factor to consider is the amount of signaling between nodes in order to keep each node updated with current conditions. Such signaling updates, particularly if frequently transmitted, drain the power of the battery-operated nodes and increase the interference in the network. It would be desirable to eliminate or at least to decrease such status update messages generated by each node in the mesh network.
The inventors further recognized that simply estimating the energy that would be used by a particular node for transmission of one hop for a packet, where energy is defined in terms of power and time, does not take into account the realities of typical ad hoc networks. Real wireless networks must deal with obstacles (buildings, walls, natural objects, weather, etc.) that cause propagation loss. So transmission energy is not an adequate measurement of the caused interference.
Accordingly, interference energy is estimated for each potential hop transmission along various routes from the source node to the destination node using an interference energy model that accounts for the factors described above. The determined interference energy for each hop is combined to produce a combined interference energy for each route. One of the routes is selected based on the combined interference energy for each route. For example, combining interference energies may include summing the interference energies, and the one route having the lowest summed interference energy may be selected.
In one non-limiting example embodiment, a transmission time associated with transmitting the packet over each hop in each of multiple routes from the source node to the destination node is determined. For each of the hops, a number of nodes that would be affected by interference produced by transmitting the packet over that hop is determined. The transmission time and the number of affected nodes for each hop are combined to produce a corresponding hop result. The hop results for each route are combined, and the one route is selected based on those combined results. For example, the transmission time and number of nodes may be multiplied and the results summed so that the one route is selected having a lowest summed result.
The transmission time preferably (though not necessarily) takes into account one or more of the following: a size of the packet, an overhead associated with sending the packet, a bit rate associated with transmitting the packet over the hop (likely determined based on current radio-related conditions for the hop), and a re-transmission probability associated with transmitting over the hop. The number of affected nodes may be estimated based on a power level at which the packet would be transmitted over the hop, a receiver threshold at which the interference is affecting other nodes, and a propagation function that translates the power level to a caused interference affecting one or more surrounding nodes. If desired, a probability that another node having data to transmit during the transmission time will actually be affected by the packet transmission may also be taken into account.
Information used to determine an interference energy associated with one or more hops may be obtained from transmissions from other nodes. Such information may also be obtained by monitoring communications between other nodes. Alternatively, it may be useful for each node to distribute determined hop interference energies among the other nodes in the mesh network.